class code5 {
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];

        Arrays.fill(isPrim,true);
        //从2开始枚举到sqrt(n) 
        for(int i=2;i<Math.sqrt(n);i++) {
            //如果当前是素数
            if(isPrim[i]) {
                //就把从i*i开始，i所有的倍数都设置为false
                for(int j=i*i;j<n;j+=i) {
                    isPrim[j] = false;
                }
            }
        }

        //统计结果
        int ret = 0;
        for(int i=2;i<n;i++) {
            if(isPrim[i]) {
                ret++;
            }
        }
        return ret;
    }
}